Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 60/115

Q:  How many different shapes does maintenance of AA-Tree need to consider?
A. 7
B. 5
C. 2
D. 3
Solution: An AA-Tree needs to consider only two shapes unlike a red-black tree which needs to consider seven shapes of transformation.
Q: In an AA-tree, we process split first, followed by a skew.
A. True
B. False
C. ...
D. ...
Solution: In an AA-tree, skew is processed first followed by a split.
Q: What is the prime condition of AA-tree which makes it simpler than a red-black tree?
A. Only right children can be red
B. Only left children can be red
C. Right children should strictly be black
D. There should be no left children
Solution: The prime condition of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.
Q: Which of the following is the correct definition for a horizontal link?
A. connection between node and a child of equal levels
B. connection between two nodes
C. connection between two child nodes
D. connection between root node and leaf node
Solution: A horizontal link is a connection between a node and a child of equal levels.
Q: AA Trees are implemented using?
A. Colors
B. Levels
C. Node size
D. Heaps
Solution: AA Trees are implemented using levels instead of colors to overcome the disadvantages of Red-Black trees.
Q: How will you remove a left horizontal link in an AA-tree?
A. by performing right rotation
B. by performing left rotation
C. by deleting both the elements
D. by inserting a new element
Solution: A left horizontal link is removed by right rotation. A right horizontal link is removed by left rotation.
Q: What are the two different operations done in an AA-Tree?
A. shift and color
B. skew and split
C. zig and zag
D. enqueue and dequeue
Solution: A skew removes a left horizontal link by right rotation and a split removes a right horizontal link by left rotation.
Q: Which of the following trees is similar to that of an AA-Tree?
A. Splay Tree
B. B+ Tree
C. AVL Tree
D. Red-Black Tree
Solution: AA- Tree is a small variation of Red-Black tree. AA-Trees overcome the complexity faced in performing insertion and deletion in Red-Black Trees.
Q: What is the worst case analysis of an AA-Tree?
A. O(N)
B. O(log N)
C. O( N log N)
D. O(N2)
Solution: The worst case analysis of an AA-Tree is mathematically found to be O(log N).
Q: Comparing the speed of execution of Red-Black trees and AA-trees, which one has the faster search time?
A. AA-tree
B. Red-Black tree
C. Both have an equal search time
D. It depends
Solution: Since an AA-tree tends to be flatter, AA-tree has a faster search time than a Red-Black tree.

You Have Score    /10